home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / incl / LEDA.020+881 / impl / olist.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  7.5 KB  |  319 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  olist.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_OLIST_H
  17. #define LEDA_OLIST_H
  18.  
  19. #include <LEDA/basic.h>
  20.  
  21. //------------------------------------------------------------------------------
  22. //
  23. //  obj_list  (doubly linked lists of obj_links)
  24. //
  25. //  each "obj_link" may be present in at most one list 
  26. //  
  27. //------------------------------------------------------------------------------
  28.  
  29. class obj_list; 
  30. class obj_link;
  31.  
  32. typedef int  (*CMP_ITEM)(obj_link*,obj_link*);
  33. typedef void (*APP_ITEM)(obj_link*);
  34. typedef int  (*ORD_ITEM)(obj_link*);
  35.  
  36. //------------------------------------------------------------------------------
  37. // class obj_link (base class for all list items)
  38. //------------------------------------------------------------------------------
  39.  
  40. class obj_link {
  41.  
  42. protected:
  43.  
  44.   obj_link* succ_link;
  45.   obj_link* pred_link;
  46.  
  47. void del_item() 
  48. { pred_link->succ_link = succ_link; 
  49.   succ_link->pred_link = pred_link; 
  50.  }
  51.  
  52. public:
  53.  
  54. //  obj_link() { succ = nil; }
  55.  
  56.   obj_link* succ_item() { return succ_link; }
  57.   obj_link* pred_item() { return pred_link; }
  58.  
  59.   friend class obj_list;
  60.   friend class c_obj_list;
  61.   friend class graph;
  62.   friend class node_list;
  63.  
  64. };
  65.  
  66.  
  67. //------------------------------------------------------------------------------
  68. // obj_list: base class for all doubly linked lists
  69. //------------------------------------------------------------------------------
  70.  
  71. class obj_list {
  72.  
  73.    obj_link* h;           // head
  74.    obj_link* t;           // tail
  75.    int count;             // length of list
  76. //
  77. // obj_link* iterator;    // iterator
  78. //
  79.  
  80. void quick_sort(obj_link**,obj_link**,CMP_ITEM);
  81.  
  82. void insertion_sort(obj_link**,obj_link**,obj_link**,CMP_ITEM);
  83.  
  84. public:
  85.  
  86.  
  87. // access operations
  88.  
  89.    int  length() const { return count; }
  90.    int  size()   const { return count; }
  91.    bool empty()  const { return (count==0) ? true : false;}
  92.  
  93.    obj_link* first()               const { return h; }
  94.    obj_link* first_item()          const { return h; }
  95.    obj_link* last()                const { return t; }
  96.    obj_link* last_item()           const { return t; }
  97.    obj_link* next_item(obj_link* p)   const { return p->succ_link; }
  98.    obj_link* succ(obj_link* p)        const { return p->succ_link; }
  99.    obj_link* pred(obj_link* p)        const { return p->pred_link; }
  100.  
  101.    obj_link* cyclic_succ(obj_link* p) const 
  102.    { return p->succ_link? p->succ_link : h; }
  103.  
  104.    obj_link* cyclic_pred(obj_link* p) const 
  105.    { return p->pred_link? p->pred_link : t; }
  106.  
  107.    obj_link* succ(obj_link* l, int i) const; 
  108.    obj_link* pred(obj_link* l, int i) const;
  109.    obj_link* get_item(int = 0)     const; 
  110.  
  111.    obj_link* max(CMP_ITEM) const;
  112.    obj_link* min(CMP_ITEM) const;
  113.    obj_link* search(obj_link*) const;
  114.  
  115.    int    rank(obj_link*) const;
  116.  
  117. // update operations
  118.  
  119.    obj_link* insert(obj_link* p, obj_link* l);
  120.    obj_link* insert(obj_link* p, obj_link* l, int dir);
  121.    obj_link* push(obj_link* p);
  122.    obj_link* append(obj_link* p);
  123.  
  124.    void del(obj_link* loc);
  125.    obj_link* pop();
  126.    obj_link* Pop();
  127.  
  128.    void   conc(obj_list&);
  129.    void   split(obj_link*,obj_list&,obj_list&);
  130.    void   apply(APP_ITEM);
  131.    void   sort(CMP_ITEM);
  132.    void   bucket_sort(int,int,ORD_ITEM);
  133.    void   permute();
  134.    void   clear();
  135.  
  136.  
  137. /* // iteration
  138.  
  139.    obj_link* set_iterator(obj_link* p) const { return (obj_link*&)iterator=p;}
  140.    obj_link* start_iteration()       const { return set_iterator(h); }
  141.    obj_link* Start_iteration()       const { return set_iterator(t); }
  142.    obj_link* move_to_succ() const { return set_iterator(iterator->succ_link); }
  143.    obj_link* move_to_pred() const { return set_iterator(iterator->pred_link); }
  144.    obj_link* read_iterator(obj_link*& x)const { return x=iterator; }
  145.    obj_link* read_iterator()         const { return iterator; }
  146.  
  147.    void  reset()               const { set_iterator(nil); }
  148.    void  init_iterator()       const { set_iterator(nil); }
  149. */
  150.  
  151.  
  152.    obj_list& operator=(const obj_list&); 
  153.    obj_list  operator+(const obj_list&); 
  154.  
  155.  
  156. // constructors & destructors
  157.  
  158.    obj_list();    
  159.  
  160.    //obj_list(const obj_list&);
  161.  
  162.   ~obj_list()  { clear(); }
  163.  
  164. };
  165.  
  166.  
  167.  
  168. inline obj_link* obj_list::push(obj_link* p)   
  169. { count++;
  170.   p->pred_link = 0;
  171.   p->succ_link = h;
  172.   if (h) 
  173.       h = h->pred_link = p;
  174.   else   
  175.       h = t =  p;
  176.   return p;
  177.  }
  178.  
  179.  
  180. inline obj_link* obj_list::append(obj_link* p)
  181. { count++;
  182.   p->pred_link = t;
  183.   p->succ_link = 0;
  184.   if (t) 
  185.       t = t->succ_link = p;
  186.   else  
  187.       t = h = p;
  188.   return p; 
  189.  } 
  190.  
  191.  
  192. inline obj_link* obj_list::pop()    
  193. { obj_link* p=h; 
  194.   if (p) 
  195.   { if (--count) 
  196.       { h = h->succ_link; 
  197.         h->pred_link = 0; 
  198.        }
  199.     else  
  200.       h = t = 0;
  201.    }
  202.   return p;
  203.  }
  204.  
  205.  
  206. inline obj_link* obj_list::Pop()    
  207. { obj_link* p=t; 
  208.   if (p)
  209.   { if (--count) 
  210.       { t = t->pred_link; 
  211.         t->succ_link = 0; 
  212.        }
  213.     else  
  214.       h = t = 0;
  215.    }
  216.   return p;
  217.  }
  218.  
  219.  
  220. inline obj_link* obj_list::insert(obj_link* n, obj_link* p) 
  221. { // insert n insert after p
  222.   obj_link* s=p->succ_link;
  223.   n->pred_link = p;
  224.   n->succ_link = s;
  225.   p->succ_link = n;
  226.   if (p==t) t=n; else s->pred_link = n;
  227.   count++;
  228.   return n;
  229. }
  230.  
  231.  
  232.  
  233.  
  234. //------------------------------------------------------------------------------
  235. //
  236. // c_obj_list (doubly linked circular object list)
  237. //
  238. // simple and efficient implementation (no counter, iterator, sorting, etc.)
  239. // removed items are assigned a nil succ pointer 
  240. // member(x) <==>  x->succ != nil
  241. //
  242. //------------------------------------------------------------------------------
  243.  
  244. class c_obj_list : public obj_link {
  245.  
  246. // the list head is an obj_link, namely the predecessor of the first 
  247. // and the successor of the last element
  248.  
  249. public:
  250.  
  251. bool empty()  const { return (succ_link==(obj_link*)this) ? true : false;}
  252.  
  253. obj_link* first()      const { return (succ_link==(obj_link*)this) ? nil : succ_link; }
  254. obj_link* last()       const { return (pred_link==(obj_link*)this) ? nil : pred_link; }
  255. obj_link* first_item() const { return first(); }
  256. obj_link* last_item()  const { return last(); }
  257.  
  258. obj_link* next_item(obj_link* p) const { return succ(p); }
  259.  
  260. obj_link* succ(obj_link* p) const 
  261. { return (p->succ_link==(obj_link*)this)? nil : p->succ_link;}
  262.  
  263. obj_link* pred(obj_link* p) const 
  264. { return (p->pred_link==(obj_link*)this)? nil : p->pred_link;}
  265.  
  266. obj_link* cyclic_succ(obj_link* p) const 
  267. { return (p->succ_link==(obj_link*)this) ? pred_link : p->succ_link; }
  268.  
  269. obj_link* cyclic_pred(obj_link* p) const 
  270. { return (p->pred_link==(obj_link*)this) ? succ_link : p->pred_link; }
  271.  
  272.  
  273.  void insert(obj_link* n, obj_link* p) 
  274.  { // insert n insert after p
  275.    obj_link* s=p->succ_link;
  276.    n->pred_link = p;
  277.    n->succ_link = s;
  278.    p->succ_link = n;
  279.    s->pred_link = n;
  280.   }
  281.  
  282.  obj_link* del(obj_link* x)
  283.  { obj_link*  p = x->pred_link;
  284.    obj_link*  s = x->succ_link;
  285.    p->succ_link = s;
  286.    s->pred_link = p;
  287.    x->succ_link = nil;
  288.    return x;
  289.   }
  290.  
  291.  bool member(obj_link* x) { return x->succ_link != nil; }
  292.  
  293.  void push(obj_link* p)   { insert(p,this); }
  294.  void append(obj_link* p) { insert(p,pred_link); }
  295.  
  296.  obj_link* pop() { return del(succ_link); }
  297.  obj_link* Pop() { return del(pred_link); }
  298.  
  299.  void clear() 
  300.  { while(succ_link != this) 
  301.    { obj_link* p = succ_link;
  302.      succ_link = p->succ_link;
  303.      p->succ_link = nil;
  304.     }
  305.    pred_link = this; 
  306.   }
  307.  
  308.  void init() { succ_link = pred_link = this; }
  309.  
  310. // constructors & destructors
  311.  
  312.  c_obj_list()  { succ_link = pred_link = this; }
  313. ~c_obj_list()  { clear(); }
  314.  
  315. };
  316.  
  317.  
  318. #endif
  319.